1. Field of the Invention
The present invention relates to distributed computing systems. More specifically, the present invention relates to a method and an apparatus for using a centralized server to coordinate assignment identifiers from multiple nodes in a distributed computing system.
2. Related Art
Computers commonly use TCP/IP (transmission control protocol/Internet protocol) to send data over a network in the form of packets. However, depending upon the structure of the network between the sender and the receiver, a data packet may be broken into smaller pieces called xe2x80x9cfragments,xe2x80x9d in a process known as xe2x80x9cfragmentation.xe2x80x9d The receiver must then re-assemble these fragments to restore the original packet. Note that fragments may arrive in any order, and fragments may arrive multiple times and possibly may not arrive.
To support fragmentation, an IP packet contains a 16-bit identification field, which uniquely identifies each packet that the sender transmits. This identification field is used to identify fragments that should be re-assembled into a single packet, and to ensure that fragments from two different packets do not get combined.
In order to accomplish this objective, the identification field must be unique for a specific sender-receiver pair using a specific protocol for the time that the associated packet may be active in the system. Rather than keeping track of identification numbers separately for each receiver, the sender typically uses sequential identification field values for each packet sent, under the assumption that the time between reuses of an identification field value will be longer than the lifetime of a packet in the network.
This simple assignment of IP identification numbers may not work well if the sender is not a single computer but is instead a cluster of computers. A cluster may include many computers working together to handle network requests.
For many purposes, it is desirable that the cluster appear to the network clients as a single machine. To accomplish this, all outgoing data packets are given a single IP address. With such an architecture, it is no longer sufficient for each node to assign sequential IP identification numbers, because two nodes may use the same number at nearly the same time, raising the potential for garbled data when a recipient attempts to recombine fragments into a packet.
One alternative is for one node in the cluster to do all the TCP/IP processing, including assigning ID numbers. However, the creates a bottleneck on this node. Performance of the cluster will be enhanced if all nodes can perform TCP/IP processing in parallel.
One solution to this problem is to partition the identification numbers between server nodes in the cluster. For example, a first node can use the numbers 1-100, a second node can use the numbers 101-200, and so on. However, this solution does not ensure that identification numbers are unique because there are only 16 bits available for identification numbers. Consequently, the identification numbers will be reused too quickly. For example, if there are 100 servers, each server would receive only 216/100=655 values, and would reuse these values in short succession, raising the probability of incorrectly combined fragments.
Another alternative is for each node in the cluster to obtain a unique identification number for each packet from a centralized server. However, this results in a performance bottleneck because each outgoing packet is delayed by the time required to retrieve the next number from the centralized server. Furthermore, the centralized server is likely to become overloaded in handling requests from many nodes.
What is needed is a method and an apparatus for efficiently assigning packet identifiers to packets from multiple nodes in a distributed computing system.
One embodiment of the present invention provides a system that uses a centralized server to coordinate assigning identifiers in a distributed computing system. The system operates by receiving a request for a block of identifiers at the centralized server from a requesting node in the distributed computing system. In response to this request, the system selects a block of identifiers from a global pool of identifiers, and then marks the global pool of identifiers to indicate that the selected block of identifiers has been assigned. The system sends the selected block of identifiers to the requesting node in order to allow the requesting node to assign identifiers from the selected block of identifiers without having to communicate with the centralized server.
In another embodiment of the present invention, upon receiving an indication that the selected block of identifiers is no longer being used by the requesting node, the system marks the global pool of identifiers to indicate that the selected block of identifiers is no longer assigned.
In another embodiment of the present invention, the system receives a subsequent request for a subsequent block of identifiers from the requesting node along with the indication that the selected block of identifiers is no longer being used.
In another embodiment of the present invention, when the selected block of identifiers is returned to the centralized server, the centralized server ensures that the selected block of identifiers is not immediately assigned again to the requesting node. This is accomplished by marking the selected block of identifiers in the global pool with an identifier for the requesting node.
In one another embodiment of the present invention, the selected block of identifiers includes an Internet Protocol (IP) identifier to be included in a header of an IP packet in order to facilitate reassembly of the IP packet.
In another embodiment of the present invention, the distributed computing system is a clustered computing system containing a plurality of nodes sharing a same IP address.
In another embodiment of the present invention, the global pool of identifiers is structured as a linked list containing blocks of identifiers.
In another embodiment of the present invention, the selected block of identifiers includes a set of consecutive identifier numbers.
In another embodiment of the present invention, the selected block of identifiers includes a set of non-consecutive identifier numbers.
In another embodiment of the present invention, sending the selected block of identifiers to the requesting node involves sending a specifier for a range of consecutive identifier numbers, wherein the specifier includes a starting value for the range and an ending value for the range.
Thus, the present invention does not suffer from the problem of the centralized server becoming overloaded because the centralized server only needs to be contacted once for each block of identifiers. This dramatically reduces the load on the centralized server. It also reduces the time required to send a packet because the centralized server does not have to be contacted before sending the packet.
The present invention also does not suffer from the problem of the IP identification numbers becoming used up too quickly in the case where only a small number of nodes are rapidly using identification numbers. For example, if a cluster of 100 nodes has two nodes currently performing network services, the above-described partitioning solution would only provide 655 packet identifiers for each node before reusing numbers. In contrast, the block solution would provide 216/2=32768 packet identifiers for each currently active node. Note that it is typically not possible to determine in advance which nodes are going to be carrying out network activity. Consequently, the partitioning solution has to divide the identification numbers between all 100 nodes, not just the two currently active nodes.